package simple.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 1995. 统计特殊四元组
 * 给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：
 * nums[a] + nums[b] + nums[c] == nums[d] ，且 a < b < c < d
 * 示例 1：
 * 输入：nums = [1,2,3,6]
 * 输出：1
 * 解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。
 * 示例 2：
 * 输入：nums = [3,3,6,4,5]
 * 输出：0
 * 解释：[3,3,6,4,5] 中不存在满足要求的四元组。
 * 示例 3：
 * 输入：nums = [1,1,1,3,5]
 * 输出：4
 * 解释：满足要求的 4 个四元组如下：
 * - (0, 1, 2, 3): 1 + 1 + 1 == 3
 * - (0, 1, 3, 4): 1 + 1 + 3 == 5
 * - (0, 2, 3, 4): 1 + 1 + 3 == 5
 * - (1, 2, 3, 4): 1 + 1 + 3 == 5
 * 提示：
 * 4 <= nums.length <= 50
 * 1 <= nums[i] <= 100
 *
 * @author 刘学松
 * @date 2021-12-29 22:59
 */
public class 统计特殊四元组 {
    public static void main(String[] args) {
        best(new int[]{1,1,1,3,5});
    }
    public int countQuadruplets(int[] nums) {
        int answer = 0;
        int length = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int b = length - 1; b > 0; b--) {
            int c = b + 1;
            for (int d = b + 2; d < length; d++) {
                map.put(nums[d] - nums[c], map.getOrDefault(nums[d] - nums[c], 0) + 1);
            }
            for (int a = 0; a < b; a++) {
                answer += map.getOrDefault(nums[a] + nums[b], 0);
            }
        }
        return answer;
    }

    public static int best(int[] nums) {
        int n = nums.length;
        // 代表x出现了几次
        int[] dp1 = new int[11];
        int[] dp2 = new int[11];
        int[] dp3 = new int[11];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (i >= 3) {
                ans += dp3[x];
            }
            if (i >= 2) {
                for (int j = 1; j <= 10 - x; j++) {
                    dp3[j + x] += dp2[j];
                }
            }
            if (i >= 1) {
                for (int j = 1; j <= 10 - x; j++) {
                    dp2[j + x] += dp1[j];
                }
            }
            dp1[x]++;

            System.out.print("dp1: ");
            for (int m : dp1) {
                System.out.print(m+",");
            }
            System.out.println();
            System.out.print("dp2: ");
            for (int m : dp2) {
                System.out.print(m+",");
            }
            System.out.println();
            System.out.print("dp3: ");
            for (int m: dp3) {
                System.out.print(m+",");
            }
            System.out.println();
            System.out.println();
        }
        return ans;
    }
}
